import time
import datetime
def insertSort(insert_list):
    if len(insert_list) == 0:
        return []
    sort_list = insert_list
    for i in range(1,len(sort_list)):#遍历未排序的数
        j = i - 1
        temp = sort_list[i]
        while j >= 0:
            if temp < sort_list[j]:
                sort_list[j + 1] = sort_list[j]
            else:
                break
            j = j - 1
        sort_list[j+1] = temp
    return sort_list

def binarySearch(insert_list,end,value):
    left = 0
    right = end - 1
    while left <= right:
        mid = left + (right - left) // 2
        if insert_list[mid] > value:
            right = mid - 1
        else:
            left = mid + 1
    return left if left < end else -1

def shellSort(insert_list):
    if len(insert_list) == 0:
        return []
    sort_list = insert_list
    gap = len(sort_list) // 2
    while gap > 0:
        gap //= 2
        for i in range(gap,len(sort_list)):#遍历未排序的数
            j = i - gap
            temp = sort_list[i]
            while j >= 0:
                if temp < sort_list[j]:
                    sort_list[j + gap] = sort_list[j]
                else:
                    break
                j = j - gap
            sort_list[j + gap] = temp
    return sort_list

def sort_swap(a,b):
    return b,a

def selectSort(insert_list):
    if len(insert_list) == 0:
        return []
    sort_list = insert_list
    for i in range(len(sort_list)):#遍历未排序的数
        min_index = i
        for j in range(i + 1,len(sort_list)):
            if sort_list[j] < sort_list[min_index]:
                min_index = j
        sort_list[min_index],sort_list[i] = sort_swap(sort_list[min_index],sort_list[i])
    return sort_list

def quickSort(insert_list,left,right):
    if len(insert_list) == 0:
        return []
    def division(insert_list,left,right):
        base = insert_list[left]
        while left < right:
            while insert_list[right] >= base and left < right:
                right -= 1
            insert_list[left] = insert_list[right]
            while insert_list[left] <= base and left < right:
                left += 1
            insert_list[right] = insert_list[left]
        insert_list[left] = base
        return left
    
    if left < right:
        base = division(insert_list,left,right)
        quickSort(insert_list,left,base-1)
        quickSort(insert_list,base+1,right)


def heapSort(input_list):
    def HeadAdjust(input_list, parent, length):
        temp = input_list[parent]
        child = 2 * parent + 1

        while child < length:
            if child + 1 < length and input_list[child] < input_list[child+1]:
                child += 1
            if temp >= input_list[child]:
                break
            input_list[parent] = input_list[child]
            parent = child
            child = 2 * parent + 1
        input_list[parent] = temp

    if len(input_list) == 0:
        return []
    sorted_list = input_list
    length = len(sorted_list)
    for i in range(0, length // 2 + 1)[::-1]:
        HeadAdjust(sorted_list, i, length)
    for j in range(1, length)[::-1]:
        temp = sorted_list[j]
        sorted_list[j] = sorted_list[0]
        sorted_list[0] = temp
        HeadAdjust(sorted_list, 0, j)
        print('第%d趟排序:' % (length - j), end = '')
        print(sorted_list)
    return sorted_list

if __name__ == '__main__':
    alist = [2,31,24,5,8,10,11,21,23,45,67,78,97,123,1234,25,356,35]
    starttime = datetime.datetime.now().microsecond 
    heapSort(alist)
    print(alist)
    endtime = datetime.datetime.now().microsecond 
    print("time cost=%d"%(endtime-starttime))
